The present invention relates generally to communication systems and more particularly relates to an apparatus for and a method of reducing the soft output information packet to be computed by a soft symbol generator that is subsequently used by a soft symbol to soft bit mapper.
In recent years, the world has witnessed explosive growth in the demand for wireless communications and it is predicted that this demand will increase in the future. There are already over 500 million users that subscribe to cellular telephone services and the number is continually increasing. Eventually, in the not too distant future the number of cellular subscribers will exceed the number of fixed line telephone installations. Already, in many cases, the revenues from mobile services already exceeds that for fixed line services even though the amount of traffic generated through mobile phones is much less than in fixed networks.
Other related wireless technologies have experienced growth similar to that of cellular. For example, cordless telephony, two way radio trunking systems, paging (one way and two way), messaging, wireless local area networks (WLANs) and wireless local loops (WLLs). In addition, new broadband communication schemes are rapidly being deployed to provide users with increased bandwidth and faster access to the Internet. Broadband services such as xDSL, short range high speed wireless connections, high rate satellite downlink (and the uplink in some cases) are being offered to users in more and more locations.
In connection with cellular services, the majority of users currently subscribe to digital cellular networks. Almost all new cellular handsets sold to customers are based on digital technology, typically second generation digital technology. Currently, third generation digital networks are being designed and tested which will be able to support data packet networks and much higher data rates. The first generation analog systems comprise the well known protocols AMPS, TACS, etc. The digital systems comprise GSM, TDMA (IS-136) or CDMA (IS-95), for example.
A diagram illustrating an example prior art communication system employing an inner and outer encoder in the transmitter, inner and outer decoding stages in the receiver and a noise source after the channel is shown in FIG. 1. The communication system, generally referenced 10, represents the typical scheme that may be used in many of the communication services described above. In such a system, the transmitter 11 comprises an encoder 14, interleaver 15, symbol generator (i.e. bit to symbol mapper) 16 and modulator 18. Input data bits 12 to be transmitted are input to the encoder 14 which may comprise an error correction encoder such as Reed Solomon, convolutional encoder, parity bit generator, etc. The encoder functions to add redundancy bits to enable errors in transmission to be located and fixed.
It is noted that both the inner and outer decoders in the receiver have complimentary encoders in the system. The outer encoder in the system comprises the encoder 14, e.g., Reed Solomon, etc. The inner encoder comprises the channel 20 which often times can be modeled as an L-symbol long FIR-type channel.
The bits output from the encoder are then interleaved wherein the order of the bits are changed so as to more efficiently combat burst errors. The rearrangement of the bits caused by interleaving improves the resistance to error bursts while adding latency and delay to the transmission.
The bits output from the interleaver are then mapped to symbols by the bit to symbol mapper 16. The bit to symbol mapper functions to transform the bits to modulator symbols. For example, an 8-PSK modulator uses 8 symbols Sk (k=0 . . . 7), hence the mapper takes three bits and converts them to one of eight symbols. Thus, the bit to symbol mapper generates a symbol for every three input bits.
The output from the mapper is input to the modulator 18 which receives symbols in the M-ary alphabet and generates the analog signal that is subsequently transmitted over the channel 20. The channel may comprise a mobile wireless channel, e.g., cellular, cordless, a fixed wireless channel, e.g., satellite, or may comprise a wired channel, e.g., xDSL, ISDN, Ethernet, etc. The processing performed in the transmitter is intended to generate a signal that can be transmitted over the channel so as to provide robust, error free detection by the receiver.
At the receiver 13, the analog signal from the channel is input to front end circuitry 22 which demodulates and samples the received signal to generate received samples y(k) 21. The samples are then input to an inner decoder 24. An example of an inner decoder is an equalizer which compensates for the ISI caused by the delay and time spreading of the channel in attempting to detect the symbols that were originally transmitted by the modulator.
Equalizers can be adapted to output hard symbol decisions or soft symbol decisions. Examples of types of commonly used hard decision equalizers include the maximum likelihood sequence estimation (MLSE) equalizer that utilize the well known Viterbi Algorithm (VA), linear equalizer and decision feedback equalizer (DFE). Examples of soft output type equalizers include Soft Output Viterbi Algorithm (SOVA) type equalizers and equalizers based on the more computational expensive Maximum A Posteriori (MAP) algorithm.
In the case of a hard decision equalizer, the output of the inner decoder comprises symbols s(k) 23 which represent hard decisions. If a soft output decoder is used, the symbols s(k) output of the inner decoder comprise soft symbol decisions. For a hard decision inner decoder, the output of the equalizer 24 along with the received samples 21 are input to a soft output generator 25 which functions to generate soft decision information 27 used by the de-interleaver. Note that depending on the type of de-interleaver, the soft output generator is adapted to generate either soft symbol information or soft bit information. In the former case, the de-interleaver must be adapted to perform symbol based de-interleaving. If the de-interleaver is adapted to perform bit based de-interleaving, the soft symbol information output from the soft output generator must first be converted to soft bit information. For example, an 8-PSK modulator uses 8 symbols Sk (k0 . . . 7), the mapper converts each symbol to three bits.
The output of the soft output generator is then input to a de-interleaver 26 which functions to restore the original order of either the symbols or the bits, depending on the type of de-interleaver used. The bits are then input to an outer decoder 29 which functions to locate and fix errors using the redundancy inserted by the encoder. The outer decoder generates the binary receive data ak 28.
Examples of the outer decoder include turbo decoders and convolutional decoders that utilize the Viterbi Algorithm. This class of decoders provides better performance by taking into account soft information about the reliability of the received symbol. The improved performance of the decoder cannot be realized, however, when soft information about the received symbols is not available. Note that the Viterbi algorithm is widely used in communication systems and has been adapted to perform functions including demodulation, decoding, equalization, etc. Many systems utilize the Viterbi Algorithm in both the inner and outer decoding stages.
As described above, the outer decoder, in some systems, is adapted to utilize the symbol decisions output from the inner decoder, e.g., the equalizer. Optimal decoders, however, require soft decisions rather than hard decisions. For example, an outer decoder that utilizes the Viterbi Algorithm to perform convolutional forward error correction decoding, requires soft decisions as input. The advantage of a Viterbi decoder is that it can efficiently process soft decision information. In order to provide soft symbol decisions, the inner decoder typically comprises a soft output equalizer such as a SOVA or MAP based equalizer.
In some cases however, such as when either a punctured code is used or bit based rather symbol based interleaving is used, soft symbol decisions cannot be used by the outer decoder. Further, it is well known that an optimal decoder requires soft bit decisions rather than hard bit decisions. Thus, optimal outer decoders require soft bit inputs rather than soft symbol inputs or hard decisions. Note that a hard decision comprises a bit value (i.e. xe2x80x980xe2x80x99 or xe2x80x981xe2x80x99) and a soft bit decision may comprise a bit value in addition to the reliability of the decision. Alternately, a soft bit decision may comprise only the reliability value for a xe2x80x981xe2x80x99 decision or alternately a xe2x80x980xe2x80x99 decision.
The problem is illustrated when considering a receiver adapted to handle a GSM EGPRS signal. Such a system utilizes a bitwise interleaver and punctured convolutional coding for performing Forward Error Correction (FEC) over channels that require equalization. Assume that the equalizer used employs a Soft Output Viterbi Algorithm in its operation and that the outer FEC decoder employs the Viterbi Algorithm. After de-interleaving, the soft symbol decision information output of the equalizer is no longer related to the bits output of the de-interleaver.
In a system employing an optimal decoder, the equalizer is adapted to provide soft outputs, i.e. soft symbol decisions. As described above, well known soft output equalizers include those based on Maximum Likelihood Sequence Detection or methods such as MAP. However, the use of such techniques is impractical in communication systems having a large symbol alphabet or those systems with channels having a time spread of several symbol periods. Such criteria demand that a reduced complexity soft output equalizer be used.
A prior art technique for generating soft bit decisions is described in xe2x80x9cA Soft-Decision State-Space Equalizer for FIR Channels,xe2x80x9d J. Thielecke, IEEE Transactions on Communications, Vol. 45, No. 10, October 1997. A nonlinear equalizer is described that is intended for FIR channels which is based on a state-space description of the channel. The algorithm utilizes equations that resemble a Kalman hard decision feedback equalizer which incorporates the probability estimates of the received bits.
A disadvantage of this prior art technique is that the level of computational complexity is very high making it difficult to implement in practical communication systems. In addition, the technique is restricted to a particular type of channel and to a particular way of describing the channel.
It is therefore desirable to further reduce the complexity of the soft symbol generator and the number of computations required to generate the soft bit information while maintaining optimal results.
The present invention is a novel and useful apparatus for and method of reducing the soft output information packet to be computed by a soft symbol generator. The reduced soft output information packet generated by the soft symbol generator is subsequently used by a soft symbol to soft bit mapper which functions to convert soft symbol decision information into soft bit decision information.
The invention is operative to construct (preferably a priori) a symbol competitor table that includes the most likely symbol competitors for each bit of the symbol. The table is populated with m entries for each possible symbol value, where m represents the number of bits per symbol. Symbol competitors are retrieved from the table in accordance with the bard decision. Soft symbol information is generated only for the symbol competitors rather than for all possible symbols thus substantially reducing the size of the information packet.
The invention permits the soft symbol generator to provide fewer soft symbol values. As described above, only m+1 (m in some cases) rather than M soft symbol values are required to compute the bit log likelihood ratios. For each symbol, the hard decision symbol is required along with m soft symbol values. The additional m soft symbol values correspond to the symbol competitors (i.e. nearest neighbors) having a bit opposite to that of the symbol corresponding to the maximum soft symbol value. For the case of 8-PSK, each hard decision has associated with it 3 competing symbols. As shown by simulations, the method of the invention provides for improved performance of several dBs.
The soft symbol information is subsequently input to a soft symbol to soft bit converter. Use of such a converter in the present invention enables the use of soft decoding in systems that incorporate a bit-wise rather than a symbol-wise interleaver. An example of such a system is the GSM Enhanced General Packet Radio System (EGPRS). The present invention is also applicable in systems wherein the encoder uses a different size alphabet than the modulator. A system may have, for example, a xc2xd rate code encoder concatenated with an 8-PSK modulator. In such a system, the soft symbol decision information output of the equalizer in the receiver does not match the type of soft decision information required by the decoder.
The method of the invention can be performed in either hardware or software. A computer comprising a processor, memory, etc. is operative to execute software adapted to perform the reduced information packet method of the present invention.
The invention provides several advantages. A key advantage is that a bit-wise or symbol-wise interleaver can be used in the system while providing soft bit information to a soft input FEC decoder, e.g., soft decoder for turbo codes, convolutional codes, etc. Another advantage of the invention is that it is independent of the type of soft symbol generator used. Thus, the invention can be used with low complexity soft output generating mechanisms as well as with full complexity SOVA type mechanisms.
Another benefit is that the approximation method and resulting table are computationally efficient in that a minimum number of arithmetic operations are required for their implementation. The symbol competitor table is relatively small and can be easily ROM based. The size of the table is Mlog2(M) for M-ary modulation. Further, the invention can be applied to any size constellations with increasingly greater benefits associated with larger constellations.
There is thus provided in accordance with the present invention a method of generating a symbol competitor table for use in reducing the complexity of an information packet used to generate soft bit values from soft symbol information for am M-ary symbol alphabet, the method comprising the steps of for each of M possible symbol decisions: for each bit position j of m bits per symbol: calculating the Euclidean distance to the M/2 symbol decisions whose bit in position j is opposite to that of the jth bit in the current symbol, selecting the symbol decision yielding a minimum Euclidean distance, placing the symbol decision in the table in accordance with the current symbol and the current bit position and wherein m, M and j are positive integers.
There is also provided in accordance with the present invention a method of reducing a soft output information packet generated by a soft symbol output generator, the method comprising the steps of pre-computing a symbol competitor table comprising the most likely symbol competitors for each possible symbol decision, looking up in the symbol competitor table, for each hard decision, the most likely symbol competitors corresponding to each of m bit positions, generating and outputting soft symbol decision values corresponding to each of the m symbol competitors and wherein m is a positive integer.
There is further provided in accordance with the present invention a method of generating soft bit decisions from hard decisions for an M-ary symbol alphabet, the method comprising the steps of pre-computing a symbol competitor table comprising the most likely symbol competitors for each possible symbol decision, looking up in the symbol competitor table, for each hard decision, the most likely symbol competitors corresponding to each of in bit positions, calculating soft output values corresponding to each symbol competitor, calculating a soft bit decision value for each of m bits as a function of the hard decision and the competitor symbols corresponding to the particular bit position and wherein m and M are positive integers.
There is also provided in accordance with the present invention a communications receiver for receiving and decoding an M-ary transmitted signal comprising a radio frequency (RF) front end circuit for receiving and converting the M-ary transmitted signal to a baseband signal, a demodulator adapted to receive the baseband signal and to generate a received signal therefrom in accordance with the M-ary modulation scheme used to generate the transmitted signal, a first decoder operative to receive the received signal and to generate a sequence of soft symbol decisions therefrom, a soft output computation module comprising processing means programmed to: pre-compute a symbol competitor table comprising the most likely symbol competitors for each possible symbol decision, look up in the symbol competitor table, for each hard decision, the most likely symbol competitors corresponding to each of m bit positions, calculate soft output values corresponding to each symbol competitor, calculate a soft bit decision value for each of m bits as a function of the hard decision and the competitor symbols corresponding to the particular bit position, a second decoder adapted to receive the soft bit values and to generate binary received data therefrom and wherein m and Mare positive integers.
There is still further provided in accordance with the present invention a computer readable storage medium having a computer program embodied thereon for causing a suitably programmed system to generate soft bit decisions from hard decisions by performing the following steps when such program is executed on the system: providing a symbol competitor table comprising the most likely symbol competitors for each possible symbol decision, looking up in the symbol competitor table, for each hard decision, the most likely symbol competitors corresponding to each of m bit positions, calculating soft output values corresponding to each symbol competitor, calculating a soft bit decision value for each of m bits as a function of the hard decision and the competitor symbols corresponding to the particular bit position and wherein m is a positive integer.
There is also provided in accordance with the present invention a method of generating soft bit decisions from hard decisions for an M-ary symbol alphabet, the method comprising the steps of generating a full soft information packet comprising a soft decision for each possible symbol in the alphabet, pre-computing a symbol competitor table comprising the most likely symbol competitors for each possible symbol decision, looking up in the symbol competitor table, for each hard decision, the most likely symbol competitors corresponding to each of q bit positions, calculating a soft bit decision value for each of q bits for the soft symbol decisions in a partial reduced soft information packet comprising soft symbol decisions corresponding to the most likely symbol competitors and wherein q and M are positive integers.